#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;


unordered_map<int, int> mp1;
unordered_map<int, int> inpos;


class TreeNode {
public:
    TreeNode* left;
    TreeNode* right;
    int val;
    TreeNode(int& v)
        :val(v)
        ,left(nullptr)
        ,right(nullptr)
    {
        
    }
    TreeNode()
        :val(0)
        , left(nullptr)
        , right(nullptr)
    {

    }
};

class Solution {
public:
    TreeNode* gettree(int pl, int pr, int il, int ir, vector<int>& preorder, vector<int>& inorder) {
        if (pl > pr || il > ir)return nullptr;
        int root_pos = pl;
        int ipos = inpos[mp1[preorder[pl]]];
        int val = preorder[pl];
        TreeNode* newroot = new TreeNode(val);
        int lnum = ipos - il;

        newroot->left = gettree(pl + 1, pl + lnum, il, ipos - 1, preorder, inorder);
        newroot->right = gettree(pl + lnum + 1, pr, ipos + 1, ir, preorder, inorder);
        return newroot;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        mp1.clear();
        inpos.clear();
        int n1 = preorder.size();
        int n2 = inorder.size();
        for (int i = 0; i < n1; i++) {
            mp1[preorder[i]] = i;
        }
        for (int i = 0; i < n2; i++) {
            inpos[mp1[inorder[i]]] = i;
        }
        return gettree(0, n1 - 1, 0, n2 - 1, preorder, inorder);

    }
};


int main() {
    vector<int> a = { 3,9,20,15,7 };
    vector<int> b = { 9,3,15,20,7 };
    Solution s;
    s.buildTree(a, b);
    return 0;
}